package com.sheng.leetcode.year2022.month10.day28;

import org.junit.Test;

import java.math.BigDecimal;
import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/10/28
 *<p>
 * 907. 子数组的最小值之和<p>
 *<p>
 * 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。<p>
 * 由于答案可能很大，因此 返回答案模 10^9 + 7 。<p>
 *<p>
 * 示例 1：<p>
 * 输入：arr = [3,1,2,4]<p>
 * 输出：17<p>
 * 解释：<p>
 * 子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。<p>
 * 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。<p>
 *<p>
 * 示例 2：<p>
 * 输入：arr = [11,81,94,43,3]<p>
 * 输出：444<p>
 *<p>
 * 提示：<p>
 * 1 <= arr.length <= 3 * 10^4<p>
 * 1 <= arr[i] <= 3 * 10^4<p>
 */
public class LeetCode0907 {

    @Test
    public void test01() {
//        int[] arr = {3,1,2,4};
        int[] arr = {11,81,94,43,3};
        System.out.println(new Solution().sumSubarrayMins(arr));
    }
}
// 暴力破解，超时
//class Solution {
//    public int sumSubarrayMins(int[] arr) {
//        int length = arr.length;
//        BigDecimal bigDecimal = new BigDecimal(0);
//        // 从 i 开始循环
//        for (int i = 0; i < length; i++) {
//            int min = arr[i];
//            // 从当前开始获取每个区域内的最小元素
//            for (int j = i; j < length; j++) {
//                min = Math.min(min, arr[j]);
//                bigDecimal = bigDecimal.add(new BigDecimal(min));
//            }
//        }
//        return bigDecimal.divideAndRemainder(new BigDecimal(1000000007))[1].intValue();
//    }
//}

class Solution {
    public int sumSubarrayMins(int[] arr) {
        // 单调栈+动态规划
        int n = arr.length;
        long res = 0;
        // 子区间最小值之和
        int[] dp = new int[n + 1];
        int[] stack = new int[n + 1];
        int top = 0;
        int mod = 1000000007;
        // 初始化
        Arrays.fill(stack, - 1);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            // 构建单调栈
            while (top > 0 && arr[i] <= arr[stack[top]]) {
                top--;
            }
            dp[i + 1] = (dp[stack[top] + 1] + (i - stack[top]) * arr[i]) % mod;
            // 入栈
            stack[++top] = i;
            res += dp[i + 1];
        }
        return (int)(res % mod);
    }
}
